package com.chj.jz.dp.class01;

public class Code04_MaximumProductSubarray {
	/**
	 * @param nums:
	 *            An array of integers
	 * @return: An integer
	 */
	public static int maxProduct(int[] nums) {
		// write your code here

		int n = nums.length;
		if (n == 0) {
			return 0;
		}

		int[] f = new int[n];
		int[] g = new int[n];
		int i;
		int res = Integer.MIN_VALUE;
		for (i = 0; i < n; i++) {
			f[i] = nums[i];
			if (i > 0) {
				f[i] = Math.max(f[i], Math.max(f[i - 1] * nums[i], g[i - 1] * nums[i]));
			}

			if (i > 0) {
				g[i] = Math.min(g[i], Math.min(f[i - 1] * nums[i], g[i - 1] * nums[i]));
			}

			res = Math.max(res, f[i]);
		}

		return res;
	}
	
	public static void main(String[] args) {
		{
			int[] arr = new int[] { 2,3,-2,4 };
			System.out.println(maxProduct(arr));
		}
		{
			int[] arr = new int[] { -1,2,4,1 };
			System.out.println(maxProduct(arr));
		}
	}
}
